package 力扣.树.中序遍历;


import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class 二叉搜索树中的众数501 {
    /**
       二叉搜索树的中序遍历：本质就是一个有序数组
      本题可以参照test包下的‘有序数组中的众数’
     */
    public int[] findMode(TreeNode root) {
          ans = new ArrayList<>();
          if (root == null){
              return null;
          }
          if (root.left == null && root.right== null){
              ans.add(root.val);
          }
          midDfs(root);
          return ans.stream().mapToInt(i -> i).toArray();


    }
    private Integer preValue = Integer.MIN_VALUE;
    private Integer preCnt = 0;
    private Integer ansCnt = 0;
    private ArrayList<Integer> ans = null;
    private void  midDfs(TreeNode root){
        if (root != null){
            midDfs(root.left);

            if (preValue == root.val){
                preCnt++;
            }else {
                preValue = root.val;
                preCnt = 1;
            }
            if (preCnt == ansCnt){
                ans.add(preValue);
            }
            if (preCnt > ansCnt){
                ans.clear();
                ans.add(preValue);
                ansCnt = preCnt;
            }

            midDfs(root.right);
        }

    }


    public int[] findMode2(TreeNode root) {
       ans2 = new ArrayList<>();
       midDfs2(root);
       int[] ans = new int[ans2.size()];
        for (int i = 0; i < ans2.size(); i++) {
            ans[i] = ans2.get(i);
        }
        return ans;
    }
    private int pre = Integer.MIN_VALUE;
    private int preCount = 0;
    private int ansCount = 0;
    private ArrayList<Integer> ans2;
    private void midDfs2(TreeNode root){
        if (root != null){
            midDfs2(root.left);

            int te = root.val;
            if (te == pre){
                preCount++;
            }else {
                pre = te;
                preCount = 1;
            }
            if (preCount >= ansCount){
                if (preCount > ansCount){
                    ans2.clear();
                    ansCount = preCount;
                }
                ans2.add(pre);
            }

            midDfs2(root.right);
        }
    }


    public int[] findMode3(TreeNode root) {
          if (root == null){
              return new int[]{};
          }
        List<Integer> ans = new ArrayList<>();
          midDfs3(root, ans);
          int[] ansReal = new int[ans.size()];
        for (int i = 0; i < ans.size(); i++) {
            ansReal[i] = ans.get(i);
        }
          return ansReal;
    }
    private int pre3 = Integer.MIN_VALUE;
    private int count3 = 0;
    private int maxCount3 = 0;
    private void midDfs3(TreeNode root, List<Integer> ans) {
        if (root != null){
            midDfs3(root.left, ans);
            if (root.val == pre3){
                count3++;
            }else {
                pre3 = root.val;
                count3 = 1;
            }
            if (count3 >= maxCount3){
                    if (count3 > maxCount3){
                        maxCount3 = count3;
                        ans.clear();//清空
                    }
                    ans.add(pre3);
            }
            midDfs3(root.right, ans);
        }
    }


}
